﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Queues;
using Algoritmia.Utils;
using Algoritmia.Utils.Numerics;

namespace Algoritmia.SemiRings
{
    public class ValueWithDecisionAndBackpointer<TValue,TDecision> : 
        IComparable<ValueWithDecisionAndBackpointer<TValue, TDecision>>
        where TValue : IComparable<TValue>
    {
        public TValue Value { get; private set; }
        public TDecision Decision { get; private set; }
        public ValueWithDecisionAndBackpointer<TValue, TDecision> Backpointer { get; private set; }

        public ValueWithDecisionAndBackpointer(TValue value, TDecision decision, 
            ValueWithDecisionAndBackpointer<TValue, TDecision> backpointer = null )
        {
            Value = value;
            Decision = decision;
            Backpointer = backpointer;
        }   

        private IEnumerable<TDecision> ToDecisionList()
        {
            var back = this;
            var lifo = AlgoritmiaFactory.Lifos<TDecision>.Default;
            while ( back.Backpointer != null)
            {
                lifo.Push(back.Decision);
                back = back.Backpointer;
            }
            return lifo;
        }

        public DataStructures.Lists.IList<TDecision> Decisions()
        {
            return ToDecisionList().ToAlgoritmiaList();
        }

        public override string ToString()
        {
            return String.Format("Value: {0} Decision: {1} Backpointer: {2}", Value, Decision,
                                 Backpointer == null ? "null" : "has");
        }

        #region Implementation of IComparable<in ValueWithDecisionAndBackpointer<TValue,TDecision>>

        public int CompareTo(ValueWithDecisionAndBackpointer<TValue, TDecision> other)
        {
            return Value.CompareTo(other.Value);
        }

        #endregion
    }

    public class MinTropicalBackpointerSemiRing<TValue,TDecision> : ISemiRing<ValueWithDecisionAndBackpointer<TValue,TDecision>>
        where TValue : IComparable<TValue>
    {
        private readonly IArithmeticsProvider<TValue> _arithmeticsProvider;
        private static MinTropicalBackpointerSemiRing<TValue, TDecision> _instance;

        private MinTropicalBackpointerSemiRing(Func<IArithmeticsProvider<TValue>> createArithmeticsProvider = null)
        {
            createArithmeticsProvider = createArithmeticsProvider ??
                                        (() => new BuiltinNumericsArithmeticsProvider<TValue>());
            _arithmeticsProvider = createArithmeticsProvider();
        }

        public static MinTropicalBackpointerSemiRing<TValue, TDecision> GetInstance()
        {
            _instance = _instance ?? new MinTropicalBackpointerSemiRing<TValue, TDecision>();
            return _instance;
        }

        #region Implementation of ISemiRing<ValueWithDecisionAndBackpointer<TValue,TDecision>>

        public ValueWithDecisionAndBackpointer<TValue, TDecision> Zero
        {
            get { return new ValueWithDecisionAndBackpointer<TValue, TDecision>(_arithmeticsProvider.MaxValue,default(TDecision)); }
        }

        public ValueWithDecisionAndBackpointer<TValue, TDecision> One
        {
            get { return new ValueWithDecisionAndBackpointer<TValue, TDecision>(_arithmeticsProvider.Zero, default(TDecision)); }
        }

        public ValueWithDecisionAndBackpointer<TValue, TDecision> Plus(ValueWithDecisionAndBackpointer<TValue, TDecision> left, 
                                                                       ValueWithDecisionAndBackpointer<TValue, TDecision> right)
        {
            return left.CompareTo(right) <= 0 ? left : right;
        }

        public ValueWithDecisionAndBackpointer<TValue, TDecision> Times(ValueWithDecisionAndBackpointer<TValue, TDecision> left, ValueWithDecisionAndBackpointer<TValue, TDecision> right)
        {
            return new ValueWithDecisionAndBackpointer<TValue, TDecision>((TValue) _arithmeticsProvider.Add(left.Value,right.Value),right.Decision,left);
        }

        #endregion
    }
}
